#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

/*
 *  动态规划类题目小结
 *  1.股票问题
 *  2.背包问题
 *  3.子串问题
 *  4.博弈问题
*/



/* 1.股票问题 */

/* 通解 
 * 状态dp本质上就是一种穷举法，我把所有情况列举出来，求出最合适的值
 * 假设有m种东西，我可以对他们分别做k种操作，得到n个结果，并且每个结果由前一次或者几次操作的结果演变而来
 * 就可以建立dp[m][k][n]
 * 股票问题带入，就是现在我有n天的时间去炒股，我可以对股票最多执行k次交易，交易必须由买入，卖出等2种操作组成，也可以保持不动，一共就是3种操作，从而得到不同的利润
 * 0：buy 买入， 1：sell 卖出，2：rest 不动
 * 建立dp[n][k][3] ，第n天，我对股票的第k次操作，是卖出用dp就是dp[n][k][2]，得到的利润为dp[n][k][2]存储的数值
 * 建立转移方程：
 * 因为每天每次操作得到的利润可以由之前的操作计算，并且相互之间有联系
 * --->      --->
 * |  |      |  |
 * sell <-> buy | 注：箭头表示状态转换方向
 * |  |      |  |
 * <---      <---
 * rest      rest
 * 我们求最大利润，所以就是求所有状态中的最大值
 * dp[n][k][0] = MAX(dp[n - 1][k][0], dp[n - 1][k - 1][1] + price[i])
 *             1.本身无股票，今天不买入股票    2.本身有股票，今天卖出股票
 * dp[n][k][1] = MAX(dp[n - 1][k][1], dp[n - 1][k][0] - price[i])
 *             1.本身由股票，今天不卖出股票    2.本身无股票，今天买入股票
 * 
 * 遍历所有情况
 * for (每一天) ：
 *   for (每一次交易)：
 *     for (每一种手段(买入/卖出)):
 *       转移方程
*/

/* 1.1 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？ */
int maxProfit(int* prices, int pricesSize) {
    int _max = 0;
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > prices[i - 1]) {
            _max = MAX(_max, prices[i] - prices[i - 1]);
            prices[i] = prices[i - 1];
        }
    }
    return _max;
}

/* 1.2 714. 买卖股票的最佳时机含手续费 */

int maxProfit(int* prices, int pricesSize, int fee){
    if (prices == NULL || pricesSize == 0) {
        return 0;
    }
    int max = 0;
    int dp[50000][2] = {0};
    /* 默认先买入第一天的股票 */
    dp[0][1] = -prices[0];
    for (int i = 1; i < pricesSize; i++) {
        dp[i][0] = MAX(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = MAX(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[pricesSize - 1][0];
}

/* 1.4 188. 买卖股票的最佳时机 IV
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int Profit(int* prices, int pricesSize) {
    int dp[pricesSize][2];
    memset(dp, 0, sizeof(dp));
    dp[0][1] = -prices[0];
    for (int i = 1; i < pricesSize; i++) {
        dp[i][0] = MAX(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = MAX(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[pricesSize - 1][0];
}

int maxProfit(int k, int* prices, int pricesSize){
    if (pricesSize == 0) return 0;
    if (k > pricesSize / 2) return Profit(prices, pricesSize);
    int dp[pricesSize][k + 1][2];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < pricesSize; i++) {
        for (int j = k; j >= 1; j--) {
            if (i - 1 == -1) {
                dp[i][j][1] = -prices[0];
                continue;
            }
            dp[i][j][0] = MAX(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = MAX(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
        }
    }
    return dp[pricesSize - 1][k][0];
}


/* 2.背包问题 */
/* 
 *   有 n 个物品和容量为 V 的背包，第 i 件物品的体积为 c[i]，价值为 w[i]。
 * 现在的目标是确定要将哪些物体放入背包，以保证在体积 不超过背包容量 的前提下，背包内的 总价值最高？
 * 
 * 共有九个小类
 * 1.01 背包问题
 * 2.完全背包问题
 * 3.多重背包问题
 * 4.混合背包问题
 * 5.二维费用背包问题
 * 6.分组背包问题
 * 7.背包问题求方案数
 * 8.求背包问题的方案
 * 9.有依赖的背包问题
 */
// 1. 01 背包问题
//约束条件：每种物品数量为 1，可以选择放或不放
/*
假设dp[i][v]表示取到第i个物品，体积为v的时候最大价值为dp[i][v];
那么取到第i个物品的时候有两种操作：①取，放入背包 ② 不放入背包
所以对应的状态转移表达式为: dp[i][v] = max{dp[i - 1][v - c[i]] + w[i], dp[i - 1][v]}
    首先，不论取或者不取，价值都是从第i-1件物品演变过来的因此第一维都是i-1
    然后如果取第i件物品，那么结果为dp[i][v] 是取了第i件物品之后的结果，价值和体积都是加上了第i件物品的
    所以我们从第i-1件物品来计算第i件的时候要减去第i件的参数(v), 即dp[i - 1][v - c[i]] v - c[i]表示取了第i件物品之后体积等于v
    不取第i件物品，那么价值直接就等于第i-1件物品

    //初始化：
    这边只有一个初始值也就是第0件物品体积为0的时候dp[0][0]肯定为0

    伪代码表示
    for (i : 0 -> n) { //表示物品种类
        for (j : 0 -> V) { //表示可以取第i件物品的体积数目，背包大小必须大于物品体积
            dp[i][v] = dp[i - 1][v]; // 取
            if (j > c[i]) //不取
                dp[i][v] = max{dp[i - 1][v - c[i]] + w[i], dp[i][v]};
        }
    }
    结果呢就是在dp[n][0...V]之中找出最大值 也就是取完n件物品之后，最大的价值
*/
//code
#define MAX_NUM 10000  // 假设数目和体积都不大与10000


int backProblem_01(int *c, int *w,int N, int V){
    int dp[MAX_NUM][MAX_NUM]; 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < V; j++) {
            dp[i][j] = dp[i - 1][j]; // 取
            if (j > c[i]) //不取
                dp[i][j] = MAX(dp[i - 1][j - c[i]] + w[i], dp[i][j]);
        }
    }
    int ret = 0;
    for (int i = 0; i < V; i++) ret = MAX(ret, dp[N][i]);
    return ret;
}

/* 
 * 优化思路:
 * 首先这个方法时间复杂度为：O(N*V) 空间复杂度为: O(N*V)
 * 我们优化一般都是选择在最耗时的地方处理，那我们看这个代码它的循环上面有没有优化空间/重复循环？有没有重复计算？ 没有
 * 空间方法，我们就需要观察这边有没有可以复用的状态？   ->   有
 * 
 * dp[i][j] = MAX(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
 * 通过观察状态转移表达式我们可以发现首先dp[i - 1][j]是可以直接变为dp[i][j]，也就是说这两个[i]是可以直接删除的,因为我们都会保留最大的那个dp[i][j]
 * 然后我们可以看到dp[i-1][j - c[i]]在我们算dp[i][j]的时候是没有被算过的，也就是说这个值还是0，如果我们要把这个第一维删掉，我们遍历顺序就要保证这个情况
 * 因此，我们可以倒过来遍历，从大到小遍历，用以保证计算dp[i][j]的时候dp[i - 1]是没有算过的, 然后遍历到c[i]位置即可，保证背包容量大于物品体积
 * 
 * 这个也就是保证了每个物品只计算一次
 * 
 * for (i : 0 -> n) { //表示物品种类
 *     for (j : V -> c[i]) { //表示可以取第i件物品的体积数目，背包大小必须大于物品体积
 * 最终结果：dp[j] = MAX(dp[j - c[i]] + w[i], dp[j]);
 * 
 */
// 这个思路其实就是自底而上的思路
// 优化后代码
int backProblem_01_(int *c, int *w,int N, int V){
    int dp[MAX_NUM]; 
    for (int i = 0; i < N; i++) {
        for (int j = V; j >= c[i]; j--) {
            dp[j] = MAX(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    return dp[N];
}

//完全背包问题
/**
 * 添加一个条件：物品可以选择无数次/k次
 * 这个一看其实思路跟上面的是一样的，就增加一个物品的个数的条件就ok了
 * 直接贴伪代码/
 * 
 *  for (i : 0 -> n) { //表示物品种类
        for (j : 0 -> V) { //表示可以取第i件物品的体积数目，背包大小必须大于物品体积
            dp[i][v] = dp[i - 1][v]; // 不取
            if (j > c[i]) // 取
                for (k : 0 -> k*c[i] < V) { // 取多少个
                    dp[i][v] = max{dp[i - 1][v - k * c[i]] + k * w[i], dp[i][v]};
                }
        }
    }
 * 
 * 根据第一步老套路优化：
 * 这边就直接套用01背包优化后代码：
 * 
 * for (i : 0 -> n) { //表示物品种类
 *     for (j : V -> c[i]) { //表示可以取第i件物品的体积数目，背包大小必须大于物品体积
 *         for (k : 1 -> k*c[i] < V) { // 取多少个
 * 最终结果：   dp[j] = MAX(dp[j - k*c[i]] + k*w[i], dp[j]);
 * 
 * 
 * 还能不能再进行优化？：
 * 这边先给伪代码：
 * 
 * for (i : 0 -> n) { //表示物品种类
 *     for (j : c[i] -> V) { //表示可以取第i件物品的体积数目，背包大小必须大于物品体积
 * 最终结果：dp[j] = MAX(dp[j - c[i]] + w[i], dp[j]);
 */

int backProblem_complate(int *c, int *w,int N, int V){
    int dp[MAX_NUM]; 
    for (int i = 0; i < N; i++) {
        for (int j = c[i]; j <= V; j++) {
            dp[j] = MAX(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    return dp[N];
}
/* 
 * 多重背包
 */



/* 
 * 二维费用背包
 */

/* 
 * 分组背包
 */

/* 
 * 有依赖的背包
 */

/* 
 * 泛化背包
 */

/* 
 * 背包问题的变化--
 */

/* 3.子串问题 */
/* 两个字符串的最长公共子序列问题 */
/**
 * "ab12d3"
 * "h5j1h2ju3"
 * 子序列 -> "123"  ->  样本行列模型
 * 此类问题不由分说，先列表
 *        0 1 2 3 4 5 6 7 8
 *      0 0 0 0 0 0 0 0 0 0
 *      1 0 0 0 0 0 0 0 0 0
 *      2 0 0 0 1 1 1 1 1 1
 *      3 0 0 0 1 1 2 2 2 2
 *      4 0 0 0 1 1 2 2 2 2
 *      5 0 0 0 1 1 2 2 2 3
 */
/* code */
int longestCommonSubsequence(char * text1, char * text2){
    int len1 = strlen(text1), len2 = strlen(text2);
    if (len1 == 0 || len2 == 0) return 0;
    int dp[len1][len2];
    for (int i = 1; i < len1; i++) {
        for (int j = 1; j < len2; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = text1[0] == text2[0] ? 1 : 0;
    for (int i = 1; i < len2; i++) {
        dp[0][i] = MAX(text1[0] == text2[i] ? 1 : 0, dp[0][i - 1]);
    }
    for (int i = 1; i < len1; i++) {
        dp[i][0] = MAX(text1[i] == text2[0] ? 1 : 0, dp[i - 1][0]);
    }
    for (int i = 1; i < len1; i++) {
        for (int j = 1; j < len2; j++) {
            dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1]);
            if (text1[i] == text2[j]) {
                dp[i][j] = MAX(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }
    return dp[len1 - 1][len2 - 1];
}

/* 寻找业务限制的模型 */
/* 咖啡问题


 */
/* 4.博弈问题 */


/* leetcode 72.编辑距离 
 * 本题实际就是求两个字符串之间的距离，那我们就定义dp[i][j]表示i到j的最短距离
 * dp[i][j] 表示word1 [0,i] 变成 word2 [0,j]的最短距离
 * dp[i - 1][j] -> dp[i][j] 表示在word1的i - 1号字符之后中插入字符word2[j]
 * dp[i][j - 1] -> dp[i][j] 表示在word2的j - 1号字符之后中插入字符word1[i] 此操作等同于直接删除word1[i]
 * dp[i - 1][j - 1] -> dp[i][j] 表示word1[i] == word2[j],不需要操作
 * 转移方程：MIN(MIN(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1])
 * dp矩阵变化  horse -> ros
 *       r     o     s
 *   0   1     2     3
 * h 1 ( 1 ) ( 2 ) ( 3 )
 * o 2 ( 2 ) ( 1 ) ( 2 )
 * r 3 ( 1 ) ( 3 ) ( 2 )
 * s 4 ( 2 ) ( 2 ) ( 2 )
 * e 5 ( 3 ) ( 3 ) ( 3 )
*/
int minDistance(char * word1, char * word2){
    int s1len = strlen(word1), s2len = strlen(word2), ret = 0;
    int dp[s1len + 1][s2len + 1];
    dp[0][0] = 0;
    for (int i = 1; i <= s1len; i++) {
            dp[i][0] = i;
    }
    for (int j = 1; j <= s2len; j++) {
            dp[0][j] = j;
    }
    for (int i = 1; i <= s1len; i++) {
        for (int j = 1; j <= s2len; j++) {
            if (word1[i - 1] != word2[j - 1]) {
                dp[i][j] = MIN(MIN(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            } else {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[s1len][s2len];
}


/* 双蛋问题 */
/*leetcode 887. 鸡蛋掉落
 * 方法1：动态规划
 * 方法2：递归
 * 
 * 问题思路：
 * 首先我们要知道如果我们拥有无限个鸡蛋，找到最小F的的最快方法为二分法，但是在鸡蛋有限的情况下并不是这样；
 * 假设我们目前只有两个鸡蛋，100层楼，我们使用二分法，寻找F，则最小F平均为50次
 * {[1, 50], [51,100]} -> 碎：1->50 不碎：51->100
 * 那么如果我们每10层楼丢一次鸡蛋，最差情况下最少花费多少次找到层数分界线F：
 * 最多19次，最少10次
 * 所以我们可以知道二分法在鸡蛋有限的情况下并不一定是最优解；
 * 那如何求出最优解呢？
 * 我们假设现在在n层丢下一个鸡蛋，会出现两种结果：1.鸡蛋碎，2.鸡蛋不碎
 * 进而把楼层区间分成两种：
 * |<-                ->|n|<-               ->|
 *           1-n-1                 n+1-N      
 * 如果鸡蛋碎了：那鸡蛋个数-1
 * 鸡蛋没碎：没有变化
 * 之后是不是回到了最初的状态：从n+1到N或者从0->n-1中求出该区间的最少次数
 * 总次数为该区间的最少次数+1
 * 写成函数即假设求次数的过程为f(k, n) = f(k, n-1)/f(k - 1, n-1) + 1
 * 因为我们要求最坏情况下的最少次数所以最坏情况：max(f(k, n-1), f(k - 1, n-1)) + 1
 * 到这里我们就求出了在n层这个高度丢第一个鸡蛋时得 最优解
 * 同样，这栋楼由n层，我们可以在任何一层丢第一次鸡蛋，所以要求全局最优解，只要吧所有层数当作第一次丢鸡蛋的起点遍历即可
 * ret 初始值设为INT_MAX即可
 * for (n : 1 -> n) {
 *    ret = min(f(k, n), ret)
 * }
*/
/* 递归做法就是把上边的思路翻译成代码 */
int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int superEggDrop(int K, int N){
    if(K == 0 || N == 0) return 0;
    if(K == 1) return N;
    if(N == 1) return 1;
    int minDrop = N + 1;
    for(int x = 1; x <= N; x ++){
        minDrop = min(minDrop, max(superEggDrop(K, N-x), superEggDrop(K-1, x-1)) + 1);
    }
    return minDrop;
}

/* 优化思路 
 * 我们粗略计算下复杂度大概是指数级别的，显而易见复杂度过高
 * 优化我们首先应该从造成复杂度高的地方入手：
 *  for(int x = 1; x <= N; x ++){
        minDrop = min(minDrop, max(superEggDrop(K, N-x), superEggDrop(K-1, x-1)) + 1);
    }
 * 暴力循环的这一段代码目的就是搜索
*/
int memo[101][10001] = {0};
int superEggDrop(int K, int N){
    if(K == 1) return N;
    if(N == 0) return 0;
    if (memo[K][N] != 0) {
        return memo[K][N];
    }
    int minDrop = INT_MAX;
    int l = 1, r = N;
    while (l <= r) {
        int mid = (l + r) / 2;
        int upVal = superEggDrop(K, N - mid);
        int downVal = superEggDrop(K - 1, mid - 1);
        if (upVal > downVal) {
            l = mid + 1;
            minDrop = min(minDrop, upVal + 1);
        } else {
            r = mid - 1;
            minDrop = min(minDrop, downVal + 1);
        }
    }
    //minDrop = min(minDrop, max(superEggDrop(K, N-l), superEggDrop(K-1, l-1)) + 1);
    memo[K][N] = minDrop;
    return minDrop;
}

/* 动态规划做法 */
int superEggDrop(int K, int N){
    int dp[K + 1][N + 1];
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j < N + 1; j++) {
            dp[i][j] = j;
        }
    }
    for (int i = 2; i < K + 1; i++) {
        for (int j = 2; j < N + 1; j++) {
            /* 暴力搜索
                for (int k = 1; k <= j; k++) {
                    dp[i][j] = MIN(dp[i][j], MAX(dp[i][j - k], dp[i - 1][k - 1]) + 1);
                }
            */
            /* 二分查找 */
            int l = 1, r = j;
            while (l < r) {
                int mid = (r + l) / 2 + 1;
                if (dp[i][j - mid] < dp[i - 1][mid - 1]) {
                    r = mid - 1;
                } else {
                    l = mid;
                }
            }
            dp[i][j] = MIN(dp[i][j], MAX(dp[i][j - l], dp[i - 1][l - 1]) + 1);
        }
    }
    return dp[K][N];
}

/* 大神做法 */
/* 学不会的做法 */
int fun(int k, int t)
{
    if (k == 1) return  t + 1;
    if (t == 1) return 2;
    return fun(k-1, t-1) + fun(k, t-1);
}

int superEggDrop(int K, int N)
{
    int result = 1;
    while(fun(K, result) <= N) {
        result++;
    }
    return result;
}




